import org.junit.Test;

import java.util.Arrays;

public class Interview08_11 {
    /**
     * 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。
     * (结果可能会很大，你需要将结果模上1000000007)
     *
     * 示例1:
     *
     *  输入: n = 5
     *  输出：2
     *  解释: 有两种方式可以凑成总金额:
     * 5=5
     * 5=1+1+1+1+1
     *
     */
    public int waysToChange(int n) {
        long[] dp = new long[n + 1];
        Arrays.fill(dp, 1);
        int[] coins = new int[]{5, 10, 25};
        for (int i = 0; i < 3; i++) {
            for (int j = coins[i]; j <= n; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return (int) (dp[n] % 1000000007);
    }

    @Test
    public void test(){
        waysToChange(61);
    }
}
